package com.company.ljh.utils;

/**
 * @description: 并查集介绍：https://zhuanlan.zhihu.com/p/468711675?
 * 并查集：多个不相交的树形结构 ，每个树都有一个根节点；
 * 并查集包括一个parent[]数组，表示当前节点的上一个节点
 * 并查集包括一个find函数，返回当前节点所在树的根节点
 * 并查集包括一个union（i，n）函数，用于将n所在的树合并到i所在树结构，合并的方式是 parent[find(n)] = find(i);表示将n所在树的根节点的前节点指向到i所在树的根节点
 *
 * @projectName:leet_code
 * @see:com.company.ljh.utils
 * @author:ljh
 * @createTime:2023/7/5 17:23
 * @version:1.0
 */

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

/**
 *
 */
public class 并查集 {
    //主结构
    public int[] parent;
    public static void main(String[] args) {
        //输入矩阵 如果节点i和节点j相连，值为1；
        int [][] isConnected = new int[][]{
            {1, 0, 0, 0, 1, 0}, // 0-0, 0-4
            {0, 1, 0, 0, 0, 1}, // 1-1, 1-5
            {0, 0, 1, 1, 0, 1}, // 2-2, 2-3, 2-5
            {0, 0, 1, 1, 0, 0}, // 3-2, 3-3
            {1, 0, 0, 0, 1, 0}, // 4-0, 4-4
            {0, 1, 1, 0, 0, 1}, // 5-1, 5-2, 5-5
        };
        并查集 test = new 并查集();
        test.initDisjointSet(isConnected);
        System.out.println(test.parent);
    }
    //初始化并查集
    public void initDisjointSet(int [][] isConnected){
        int nodeSize = isConnected.length;
        parent = new int[nodeSize];
        //对节点进行初始化，每个节点父节点指向自己
        for(int i =0;i<nodeSize;i++){
            parent[i] = i;
        }
        //通过图对并查集进行合并
        for(int i=0;i<nodeSize;i++){
            for(int j = i+1;j < nodeSize;j++){
                if (isConnected[i][j] == 1)
                    //将节点i所在树合并到节点i
                    union(i,j);
            }
        }
    }
    //递归查找节点的根节点
    private int find(int x){
        //当前节点的父节点等于当前节点，表面当前节点就是父节点
        if(parent[x] == x){
            return x;
        }else{
            //查找父节点的根节点
           //return  find(parent[x]);
           //可作路径压缩，将当前节点的父节点指向父节点的父节点,保证每一个节点指向的都是树的根节点
            parent[x] = find(parent[x]);
            return parent[x];
        }
    }
    private void union(int i, int j) {
        //合并逻辑，将j节点的根节点的根节点指向i节点的根节点
        parent[find(j)] = find(i);
    }
}
